Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices

摘要

Randomness is a vital resource for modern day information processing,especially for cryptography. A wide range of applications critically rely onabundant, high quality random numbers generated securely. Here we show how toexpand a random seed at an exponential rate without trusting the underlyingquantum devices. Our approach is secure against the most general adversaries,and has the following new features: cryptographic level of security, toleratinga constant level of imprecision in the devices, requiring only a unit sizequantum memory per device component for the honest implementation, and allowinga large natural class of constructions for the protocol. In conjunct with arecent work by Chung, Shi and Wu, it also leads to robust unbounded expansionusing just 2 multi-part devices. When adapted for distributing cryptographickeys, our method achieves, for the first time, exponential expansion combinedwith cryptographic security and noise tolerance. The proof proceeds by showingthat the Renyi divergence of the outputs of the protocol (for a specificbounding operator) decreases linearly as the protocol iterates. At the heart ofthe proof are a new uncertainty principle on quantum measurements, and a methodfor simulating trusted measurements with untrusted devices.